package A_sort;

public class Questions {


    /**
     * 异或相关问题 ： 在一个数组中 arr[] 有一种数字 出现了奇数次数 其他数字出现了偶数次数 1：找出现了奇数次的数字
     * 2：有两种数字出现了奇数次 其他数字出现了偶数次 找出现奇数次数的数字
     * 要求时间复杂度 O(N) 空间复杂度 O(1)
     *
     * @param arr
     */
    public static int findOddNumber1(int[] arr) {
        int result = 0;
        for (int cur : arr) {
            result ^= cur;
        }
        return result;
    }

    public static int[] findOddNumber2(int[] arr) {
        int temp = 0;
        int[] result = new int[2];
        for (int cur : arr) {
            temp ^= cur;
        }
        int res = temp & (~temp + 1);
        for (int cur : arr) {
            if ((res & cur) == 1) {
                res ^= cur;
            }
        }
        result[0] = res ^ temp;
        result[1] = res;
        return result;
    }


    /**
     * 在一个有序数组中 查询某个数是否存在
     * 关键词 二分法
     * 时间复杂度 O(logN)
     *
     * @param arr
     * @param num
     */
    public static boolean findNumber(int[] arr, int num) {
        if (arr == null || arr.length == 0) {
            return false;
        }
        int i = 0, j = arr.length - 1;
        while (i <= j) {
            int mid = (i + j) / 2;
            if (num == arr[mid]) {
                return true;
            }
            if (arr[mid] > num) {
                j = mid - 1;
            }
            if (arr[mid] < num) {
                i = mid + 1;
            }
        }
        return false;
    }

    /**
     * 在一个有序数组中 查询大于等于某个数最左侧的数字
     * 关键词 二分法
     * 时间复杂度 O(logN)
     *
     * @param arr
     * @param num
     */
    public static int findLeftNumber(int[] arr, int num) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        int i = 0, j = arr.length - 1, temp = 0;
        while (i <= j) {
            int mid = (i + j) / 2;
            if (arr[mid] >= num) {
                j = mid - 1;
                temp = mid;
            } else {
                i = mid + 1;
            }
            if (i == temp) {
                return temp;
            }
        }
        return -1;
    }


    /**
     * 局部最小值 ：arr.length = N 对于下标0位置 arr[0]<arr[1] arr[0]为局部最小;arr[N-2]<arr[N-1] arr[N]为局部最小;arr[i-1]>arr[i]<arr[i+1] arr[i]为局部最小
     * 无序数组arr任意相邻两个元素不相等 求一个局部最小的位置即可
     * 要求时间复杂度 O(N)
     *
     * @param arr
     */
    public static int findPartMin(int[] arr) {
        if (arr == null || arr.length < 2) {
            return -1;
        }
        if (arr[0] < arr[1]) {
            return 0;
        }
        if (arr[arr.length - 1] < arr[arr.length - 2]) {
            return arr.length - 1;
        }
        int i = 0, j = arr.length - 1;
        while (i <= j) {
            int mid = (i + j) / 2;
            if (arr[mid - 1] > arr[mid] && arr[mid] < arr[mid + 1]) {
                return mid;
            }
            if (arr[mid - 1] < arr[mid]) {
                j = mid;
            }
            if (arr[mid + 1] < arr[mid]) {
                i = mid;
            }
        }
        return -1;
    }


    /**
     * 求数组arr L - R 下标范围的最大值(L<R)
     * 二分 多叉树 递归 栈
     * master公式 T(N)=a*(N/b)+O(N^d) 一般情况算递归的时间复杂度（子问题规模相等）
     * T(N) 母问题数据量   a 调用递归次数 b 调用递归子问题的数据量 d 剩余部分时间复杂度
     * logba(以b为底a的对数)<d = O(N^d)
     * logba(以b为底a的对数)>d = O(N^(logba))
     * logba(以b为底a的对数)=d = O(N^d*logN)
     * 本题 a=2,b=2,d=0 时间复杂度为 O(N)
     *
     * @param arr
     * @param L
     * @param R
     * @return
     */
    public static int findMax(int[] arr, int L, int R) {
        if (L == R) {
            return arr[L];
        }
        int mid = L + ((R - L) >> 1);
        int leftMax = findMax(arr, L, mid);
        int rightMax = findMax(arr, mid + 1, R);
        return Math.max(leftMax, rightMax);
    }


    /**
     * 小和问题
     * 归并
     * 小和：在数组当中每一位数左侧小于改数字的所有数字的和
     * 思路：转换为遍历每一位，右侧出现几个比当前位置的数字大的数字，该数字加几次
     * eg：[1,3,4,2,5] 1小和0,3小和1,4小和1+3=4,2小和1,5小和1+3+4+2 =10 总计 0+1+4+1+10 = 16
     * 转换为 1右边有4个数字比1大 1*4,3右边2个数字比3大 3*2，4右边有1个数字比4大 4*1 ，2右边有1个数字比2大 2*1 总计 1*4+3*2+4*1+2*1 = 16
     * 二分               [1,3,4,2,5]
     * ↓   ↓
     * [1,3,4]        [2,5]
     * ↓              ↓
     * [1,3]   [4]       [2] [5]
     * ↓
     * [1] [3]
     * ------------------------------------
     * 比较         ↑ 1<3↑             ↑ 2<5↑   2
     * [1]                [2,5]     1
     * -----------------------------
     * [1,3]  1<4[4]                1
     * ↑         ↑
     * [1]
     * -----------------------------
     * [1,3]  3<4[4]                3
     * ↑       ↑
     * [1,3,4]            [2,5]
     * ↑         1<2      ↑        1
     * ↑       3>2      ↑
     * ↑       3<5        ↑      3
     * ↑     4<5        ↑      4
     * [1,2,3,4,5]             16
     */
    public static int smallSum(int[] arr) {
        if (arr == null || arr.length < 1) {
            return 0;
        }
        return smallSumProcess(arr, 0, arr.length - 1);
    }

    private static int smallSumProcess(int[] arr, int L, int R) {
        if (L == R) {
            return 0;
        }
        int mid = L + ((R - L) >> 1);
        int leftSum = smallSumProcess(arr, L, mid);
        int rightSum = smallSumProcess(arr, mid + 1, R);
        int sum = leftSum + rightSum;
        return smallSumMerge(arr, L, mid, R, sum);
    }

    private static int smallSumMerge(int[] arr, int L, int M, int R, int sum) {
        int tempPoint = 0;
        int[] temp = new int[R - L + 1];
        int leftPoint = L;
        int rightPoint = M + 1;
        while (leftPoint <= M && rightPoint <= R) {
//            if (arr[leftPoint]<arr[rightPoint]){
//                sum=sum+arr[leftPoint]*(R-rightPoint+1);
//                temp[tempPoint]=arr[leftPoint];
//                leftPoint++;
//                tempPoint++;
//                continue;
//            }else if (arr[leftPoint]>=arr[rightPoint]){
//                temp[tempPoint]=arr[rightPoint];
//                rightPoint++;
//                tempPoint++;
//                continue;
//            }
            sum += arr[leftPoint] < arr[rightPoint] ? sum + arr[leftPoint] * (R - rightPoint + 1) : 0;
            temp[tempPoint++] = arr[leftPoint] < arr[rightPoint] ? arr[leftPoint++] : arr[rightPoint++];
        }
        while (leftPoint <= M) {
            temp[tempPoint++] = arr[leftPoint++];
        }
        while (rightPoint <= R) {
            temp[tempPoint++] = arr[rightPoint++];
        }
        for (int i = 0; i < temp.length; i++) {
            arr[L + i] = temp[i];
        }
        return sum;
    }


    /**
     * 逆序对问题
     * 逆序对：在一个数组中，如果左边的数比右边的数大 则这两个数构成一个逆序对
     * 打印所有逆序对/打印逆序对个数
     * 归并
     */
    public static int reversePare(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        return reversePareProcess(arr, 0, arr.length - 1);
    }

    private static int reversePareProcess(int[] arr, int L, int R) {
        if (L == R) {
            return 0;
        }
        int mid = L + ((R - L) >> 1);
        int leftCount = reversePareProcess(arr, L, mid);
        int rightCount = reversePareProcess(arr, mid + 1, R);
        int count = leftCount + rightCount;
        return reversePareMerge(arr, L, mid, R, count);
    }

    private static int reversePareMerge(int[] arr, int L, int M, int R, int count) {
        int[] temp = new int[R - L + 1];
        int tempPoint = 0;
        int leftPoint = L;
        int rightPoint = M + 1;
        while (leftPoint <= M && rightPoint <= R) {
            count += arr[leftPoint] > arr[rightPoint] ? (rightPoint - M) : 0;
            temp[tempPoint++] = arr[leftPoint] <= arr[rightPoint] ? arr[leftPoint++] : arr[rightPoint++];
        }
        while (leftPoint <= M) {
            temp[tempPoint++] = arr[leftPoint++];
        }
        while (rightPoint <= R) {
            temp[tempPoint++] = arr[rightPoint++];
        }
        for (int i = 0; i < temp.length; i++) {
            arr[L + i] = temp[i];
        }
        return count;
    }


    /**
     * 荷兰国旗问题
     * 问题1
     * 给定一个数组 arr 和一个数字 num 请把小于等于num的数字放在数组的左边，大于num的数放在数组的右边
     * 要求空间复杂度O(1) 时间复杂度O(N)
     *
     * 问题2
     * 给定一个数组 arr 和一个数字 num 请把小于num的数字放在数组左边，大于num的数放在数组右边，等于num的数放在数组中间
     * 要求空间复杂度O(1) 时间复杂度O(N)
     */


    public static int[] theNetherlandsFlag1(int[] arr,int num){
        //小于等于num数组区域的边界
        int index=-1;
        for (int i = 0; i < arr.length;i++) {
            //如果arr[i]<= num
            //则将arr[i]和小于等于区的下一个数字交换
            //i++,index++
            if (arr[i]<=num){
                Swap.swap(arr,i,index+1);
                index++;
            }
            //如果大于num 直接下一位
        }
        return arr;
    }

    public static int[] theNetherlandsFlag2(int[] arr,int num){
        //小于num数组区域的边界
        int smallIndex = -1;
        //大于num数组区域的边界
        int bigIndex = arr.length;
        for (int i = 0; i < arr.length;) {
            if (i==bigIndex-1){
                break;
            }
            //如果arr[i]<num
            //则将arr[i]和小于区的下一个数字交换
            //i++,smallIndex++
            if(arr[i]<num){
                Swap.swap(arr,i,smallIndex+1);
                smallIndex++;
                i++;
                continue;
            }
            //如果arr[i]==num
            //i++
            if (arr[i]==num){
                i++;
                continue;
            }
            //如果arr[i]>num
            //则将arr[i]和大于区的前一个数交换
            //bigIndex--,i不变
            if(arr[i]>num){
                Swap.swap(i,bigIndex-1,arr);
                bigIndex--;
                continue;
            }

        }
        return arr;
    }


    public static void main(String[] args) {
        int[] a = {3,5,6,3,4,5,2,6,9,0};
        a=theNetherlandsFlag2(a,5);
        System.out.println(1);
    }
}
